#include <iostream>
using namespace std;

//最大哈夫曼节点结构体数组个数
const int  MAX_NODE = 100;
//最大哈夫曼编码结构体数组个数
const int MAX_CODE = 100;
//最大字符编码数组长度
const int  MAX_CODE_LEN = 100;

typedef struct Node
{
    double weight;
    char ch;
    int parent;
    int lchild;
    int rchild;
}HuNode;

typedef struct Code
{
    int code[MAX_CODE_LEN];
    int start;
}HuCode;

HuNode tree[MAX_NODE];
HuCode code[MAX_CODE];

void HuffmanTree(int n)
{
    //哈夫曼节点初始化
    for (int i = 0; i < n * 2 - 1; ++i)
    {
        tree[i].parent = -1;
        tree[i].lchild = -1;
        tree[i].rchild = -1;
    }

    for (int i = 0; i < n; i++)
    {
        cout << "请输入第个" << i + 1 << "哈夫曼字符和权重" << endl;
        cin >> tree[i].ch >> tree[i].weight;
    }

    int x1, x2;
    double w1, w2;

    //每次找出最小的权重的节点，生成新的节点，需要n - 1次合并
    for (int i = 0; i < n - 1; i++)
    {
        x1 = x2 = -1;
        w1 = w2 = DBL_MAX;
        //n + i次遍历找权值最小的两个结点x1和x2（Select函数需求）
        for (int j = 0; j < n + i; ++j)
        {
            //得到最小权重的节点
            if (tree[j].parent == -1 && tree[j].weight < w1)
            {
                //如果更新了最小的结点，那么需要把上次最小的给第二个最小的结点
                w2 = w1;
				x2 = x1;

                x1 = j;
                w1 = tree[j].weight;
            }
            else if (tree[j].parent == -1 && tree[j].weight < w2)
            {
                x2 = j;
                w2 = tree[j].weight;
            }
        }
        //找到最小的两个节点后合并成一个新的节点
        tree[n + i].lchild = x1;
        tree[n + i].rchild = x2;
        tree[n + i].weight = w1 + w2;
        tree[x1].parent = n + i;
        tree[x2].parent = n + i;
    }
}

//打印每个字符的哈夫曼编码
void HuffmanCode(int n)
{
    //保存当前叶子节点的字符编码
    HuCode hCode;
    //当前父节点
    int parent;
    //下标和叶子节点的编号
    int index;

    for (int i = 0; i < n; ++i)
    {
        hCode.start = n - 1;
        index = i;
        parent = tree[i].parent;
        //遍历的条件是父节点不等于-1
        while (parent != -1)
        {
            //先拿到父节点，然后判断左节点是否为当前值，如果是取节点0，否则取节点1
            if (tree[parent].lchild == index)
            {
                hCode.code[hCode.start] = 0;
            }
            else
            {
                hCode.code[hCode.start] = 1;
            }
            hCode.start--;
            index = parent;
            parent = tree[index].parent;
        }
        //把当前的叶子节点信息保存到编码结构体里面
        for (int j = hCode.start + 1; j < n; ++j)
        {
            code[i].code[j] = hCode.code[j];
        }
        code[i].start = hCode.start;
    }

}

int main()
{
    cout << "请输入哈夫曼字符个数：";
    int n = 0;
    cin >> n;
    if (n <= 0)
    {
        cout << "您输入的个数有误！" << endl;
        return -1;
    }

    HuffmanTree(n);
    HuffmanCode(n);

    for (int i = 0; i < n; ++i)
    {
        cout << tree[i].ch << ": Huffman Code is:";
        for (int j = code[i].start + 1; j < n; ++j)
        {
            cout << code[i].code[j];
        }
        cout << endl;
    }

    system("pause");
    return 0;
}